import java.util.Arrays;

public class TextDemo {

    private static int partition(int[] array,int left,int right){
        int d = left+1;
        int tem = array[left];
        for(int i =left+1;i<=right;i++){
            if(array[i]<tem){
                swap(array,i,d);
                d++;
            }
        }
        swap(array,d-1,left);
        return d-1;
    }
    //从后面找小于tem的
    private static int partition1(int[] array,int left,int right){
        int prevIndex = left;
        int currentIndex = left+1;
        while(currentIndex <= right){
            if(array[currentIndex]<array[left] && array[++prevIndex]!=array[left]){
                swap(array,currentIndex,prevIndex);
            }
            currentIndex++;
        }
        swap(array,prevIndex,left);
        return prevIndex;
    }
    private static int partitionDepth(int[] array,int left,int right){
        int i = left;
        int tem = array[i];
        while(left<right){
            while(left<right && array[right]>=tem){
                right--;
            }
            array[left] = array[right];
            while(left<right && array[left]<=tem){
                left--;
            }
            array[right] = array[left];
        }
        array[left] = tem;
        return left;
    }
    private static int partitionHoare(int[] array,int left,int right){
        int i = left;
        int tem = array[i];
        while(left<right){
            while(left<right && array[right]>=tem){
                right--;
            }
            while(left<right && array[left]<=tem){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
    private static void quick(int[] array,int left,int right){
        if(left>=right){
            return ;
        }
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    private static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void maxHeapSort(int[] array){
        buildHeap(array);
        for(int i = array.length-1;i>0;i--){
            swap(array,0,i);
            maxHeapify(array,0,i);
        }
    }
    private static void buildHeap(int[] array){
        for(int i = array.length/2-1;i>0;i--){
            maxHeapify(array,i,array.length);
        }
    }
    private static void maxHeapify(int[] array,int i,int heapSize){
        int left = 2*i+1;
        int right = left+1;
        int last = i;
        if(left<heapSize && array[left]>array[last]){
            last = left;
        }
        if(right<heapSize && array[right]>array[last]){
            last = right;
        }
        if(last!=i){
            swap(array,last,i);
            maxHeapify(array,last,heapSize);
        }
    }
    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
    public static void shell(int[] array){
        for(int gap = array.length/2;gap>0;gap/=2){
            for(int groupStartIndex = 0;groupStartIndex<gap;groupStartIndex++){
                for(int currentIndex = groupStartIndex;currentIndex<array.length;currentIndex+=gap){
                    int currentNumber = array[currentIndex];
                    int prevIndex = groupStartIndex-gap;
                    while(prevIndex>groupStartIndex && array[prevIndex]<currentNumber){
                        array[prevIndex+gap] = array[prevIndex];
                        prevIndex-=gap;
                    }
                    array[prevIndex+gap] = array[prevIndex];
                }
            }
        }
    }
    public static void shellSort(int[] array){
        for(int gap = array.length/2;gap>0;gap/=2){
            for(int i = gap;i< array.length;i++){
                int currentNumber = array[i];
                int prevIndex = i-gap;
                while(prevIndex>=0 && currentNumber<array[prevIndex]){
                    array[prevIndex+gap] = array[prevIndex];
                    prevIndex-=gap;
                }
                array[prevIndex+gap] = currentNumber;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 2, 1, 3, 5, 4};
        quickSort(arr);
        // 输出: [1, 2, 3, 4, 5, 6]
        System.out.println(Arrays.toString(arr));


    }
}
